﻿using System;
using System.Collections.Generic;
using Library.Collections.Generic;
using INDEX = System.UInt64;

namespace Library.Linq
{
    internal enum OpCode
    {
        Nop = 0,
        Call = 1,
        Push = 2,
        Pop = 3
    }
    internal struct Instruction
    {
        public OpCode OpCode;
        public object Operand;
    }

    public static class BreadthFirst
    {
        static void Resize<T>(ref T[] array, ref int head, ref int tail, int count, int capacity)
        {
            if (capacity == array.Length)
                return;

            if (capacity < count)
                throw new InvalidOperationException();

            T[] new_array = new T[capacity];
            if (count > 0)
            {
                int length_from_head = array.Length - head;

                Array.Copy(array, head, new_array, 0, Math.Min(count, length_from_head));
                if (count > length_from_head)
                    Array.Copy(array, 0, new_array, length_from_head, count - length_from_head);
            }

            array = new_array;
            tail = count;
            head = 0;
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode>(TNode tree)
            where TNode : ITreeReadOnly<TNode>
        {
            return AsEnumerable(tree, new Library.Collections.Generic.Stack<TNode>());
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode>(TNode tree, IStack<TNode> stack)
            where TNode : ITreeReadOnly<TNode>
        {
            Instruction[] program = new Instruction[0];
            int head = 0;
            int tail = 0;
            int count = 0;
            TNode root = tree;

            try
            {
                if (!stack.Push(tree)) yield break;
                yield return (IEnumerable<TNode>)stack.Clone(Direction.Reverse, Access.Read);

                foreach (var child in tree.Children)
                {
                    if (count == program.Length || tail == program.Length)
                        Resize(ref program, ref head, ref tail, count, Math.Max(Math.Max(count, tail) * 2, 4));

                    program[tail].OpCode = OpCode.Call;
                    program[tail].Operand = child;

                    if (++tail == program.Length)
                        tail = 0;

                    count++;
                }

                foreach (var item in stack)
                {
                    if (count == program.Length || tail == program.Length)
                        Resize(ref program, ref head, ref tail, count, Math.Max(Math.Max(count, tail) * 2, 4));

                    program[tail].OpCode = OpCode.Pop;
                    program[tail].Operand = item;

                    if (++tail == program.Length)
                        tail = 0;

                    count++;
                }

                goto label6;
            label1:
                if (!stack.Push(tree)) goto label6;

                yield return (IEnumerable<TNode>)stack.Clone(Direction.Reverse, Access.Read);

                using (var children = tree.Children.GetEnumerator())
                {
                    if (children.MoveNext())
                    {
                        using (var enumerator = stack.GetEnumerator(Direction.Reverse))
                        {
                        label2:
                            if (enumerator.MoveNext())
                            {
                                var item = enumerator.Current;

                                if (count > 0)
                                {
                                    int ntail = tail > 0 ? tail - 1 : program.Length - 1;
                                    if (program[ntail].OpCode == OpCode.Pop && object.ReferenceEquals(program[ntail].Operand, item))
                                    {
                                        tail = ntail;
                                        program[tail].Operand = null;
                                        count--;
                                        goto label2;
                                    }
                                }
                            label3:
                                if (count == program.Length || tail == program.Length)
                                    Resize(ref program, ref head, ref tail, count, Math.Max(Math.Max(count, tail) * 2, 4));

                                program[tail].OpCode = OpCode.Push;
                                program[tail].Operand = item;

                                if (++tail == program.Length)
                                    tail = 0;

                                count++;

                                if (enumerator.MoveNext())
                                {
                                    item = enumerator.Current;
                                    goto label3;
                                }
                            }
                        }
                        do
                        {
                            TNode child = children.Current;

                            if (count == program.Length || tail == program.Length)
                                Resize(ref program, ref head, ref tail, count, Math.Max(Math.Max(count, tail) * 2, 4));

                            program[tail].OpCode = OpCode.Call;
                            program[tail].Operand = child;

                            if (++tail == program.Length)
                                tail = 0;

                            count++;
                        }
                        while (children.MoveNext());

                        foreach (var item in stack)
                        {
                            if (count == program.Length || tail == program.Length)
                                Resize(ref program, ref head, ref tail, count, Math.Max(Math.Max(count, tail) * 2, 4));

                            program[tail].OpCode = OpCode.Pop;
                            program[tail].Operand = item;

                            if (++tail == program.Length)
                                tail = 0;

                            count++;
                        }
                    }
                }
                stack.Pop();

            label6:
                if (count > 0)
                {
                    OpCode opCode = program[head].OpCode;
                    if (opCode == OpCode.Call)
                    {
                        tree = (TNode)program[head].Operand;
                        program[head].Operand = null;
                        if (++head == program.Length)
                            head = 0;
                        count--;
                        goto label1;
                    }
                    else if (opCode == OpCode.Pop)
                    {
                        TNode popped;
                        if (!stack.Pop(out popped)) throw new Exception();
                        if (object.ReferenceEquals(root, popped)) yield break;
                        popped = default(TNode);
                    }
                    else if (opCode == OpCode.Push)
                    {
                        if (!stack.Push((TNode)program[head].Operand))
                        {
                            object operand = program[head].Operand;

                        label7:
                            program[head].Operand = null;
                            if (++head == program.Length)
                                head = 0;
                            count--;

                            if (count > 0)
                            {
                                if (program[head].OpCode == OpCode.Pop && object.ReferenceEquals(operand, program[head].Operand))
                                {
                                    program[head].Operand = null;
                                    if (++head == program.Length)
                                        head = 0;
                                    count--;
                                    goto label6;
                                }
                                else goto label7;
                            }
                            else yield break;
                        }
                    }
                    program[head].Operand = null;
                    if (++head == program.Length)
                        head = 0;
                    count--;
                    goto label6;
                }
            }
            finally
            {
                program = null;
            }
        }
    }
}
